package com.cat.dataStructure;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/the-number-of-the-smallest-unoccupied-chair/
 * @create 2025/10/6 17:38
 * @since JDK17
 */

public class Solution100 {
    public int smallestChair(int[][] times, int targetFriend) {
        PriorityQueue<Integer> chairs = new PriorityQueue<>();
        PriorityQueue<int[]> event = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            } else { // 离开事件排前面
                return a[2] - b[2];
            }
        });
        int n = times.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            var time = times[i];
            chairs.add(i);  // 椅子
            event.add(new int[]{i, time[1], 0});    // 离开事件
            event.add(new int[]{i, time[0], 1});    // 进来事件
        }

        while (!event.isEmpty()) {
            int[] e = event.poll();
            if (e[2] == 1) {    // 来了一个
                int chair = chairs.poll();  // 弹出一个
                map.put(e[0], chair);
                if (e[0] == targetFriend) {
                    return chair;
                }
            } else {    // 出去一个
                chairs.add(map.get(e[0]));
            }
        }

        return -1;
    }
}
